package com.github.yangyishe.p100;

/**
 * 此方案的时间复杂度为O(m+n)
 */
public class Problem04S2 {
    public static void main(String[] args) {
        int[] nums1=new int[]{4,5,6,8,9};
        int[] nums2=new int[]{};

        Problem04S2 problem04S2 = new Problem04S2();
        double medianSortedArrays = problem04S2.findMedianSortedArrays(nums1, nums2);
        System.out.println("medianSortedArrays = " + medianSortedArrays);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //1。 分别在nums1和nums2创建left,right指针(左右均为闭区间)
        int left1=0;
        int right1=nums1.length-1;
        int left2=0;
        int right2= nums2.length-1;

        //2. 遍历m,n的边界元素,逐次删除最大元素和最小元素
        while((right1-left1)+(right2-left2)>0){
            if(right1==left1-1){
                return ((double)(nums2[(left2+right2)/2]+nums2[(left2+right2+1)/2]))/2;
            }
            if(left2-1==right2){
                return ((double)(nums1[(left1+right1)/2]+nums1[(left1+right1+1)/2]))/2;
            }
            if(nums1[left1]>nums2[left2]){
                left2++;
            }else{
                left1++;
            }
            if(nums1[right1]>nums2[right2]){
                right1--;
            }else{
                right2--;
            }
        }

        //3. 当剩余的数量<=2时停止遍历,获取中值
        if(right1==left1-1){
            return ((double)(nums2[left2]+nums2[right2]))/2;
        }
        if(left2-1==right2){
            return ((double)(nums1[left1]+nums1[right1]))/2;
        }

        return ((double)(nums1[left1]+nums2[left2]))/2;
    }
}
